package org.example.algorithm.binarytree;

import javafx.util.Pair;
import org.example.algorithm.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

//    4
//  9  0
// 5 1
public class SumNumbersSolution {
    private int sum = 0;

    public static void main(String[] args) {

    }

    //双队列实现
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        Queue<Integer> preValueQueue = new LinkedList<>();
        int sum = 0;
        treeNodeQueue.offer(root);
        preValueQueue.offer(root.val);
        while (!treeNodeQueue.isEmpty()) {
            TreeNode node = treeNodeQueue.poll();
            int preValue = preValueQueue.poll();
            if (node.left==null && node.right==null) {
                sum += preValue;
            }
            if (node.left != null) {
                treeNodeQueue.offer(node.left);
                preValueQueue.offer(node.left.val + 10 * preValue);
            }
            if (node.right != null) {
                treeNodeQueue.offer(node.right);
                preValueQueue.offer(node.right.val + 10 * preValue);
            }
        }
        return sum;
    }

    //递归实现
    public int sumNumbers3(TreeNode root) {
        dfs(root, 0);
        return sum;
    }

    private void dfs(TreeNode root, int preValue) {
        if (root == null) {
            return;
        }
        int tempValue = root.val + preValue * 10;
        if (root.left == null && root.right == null) {
            sum += tempValue;
        }
        dfs(root.left, tempValue);
        dfs(root.right, tempValue);
    }

    //单队列实现
    public int sumNumbers2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair(root, 0));
        while (!queue.isEmpty()) {
            Pair nodePair = queue.poll();
            TreeNode node = (TreeNode) nodePair.getKey();
            Integer parentVal = (Integer) nodePair.getValue();
            int temp = node.val + parentVal * 10;
            if (node.left == null && node.right == null) {
                sum += temp;
            }
            if (node.left != null) {
                queue.offer(new Pair(node.left, temp));
            }
            if (node.right != null) {
                queue.offer(new Pair(node.right, temp));
            }
        }
        return sum;
    }
}
